package dp.dajiajieshe;
//337. 打家劫舍 III

import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}public class Num337_rob {
    Map<TreeNode , Integer> f = new HashMap<>();//存储选中该节后，最大值
    Map<TreeNode , Integer> g = new HashMap<>();//存储不选中该节后，最大值
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root , 0) , g.getOrDefault(root , 0));
    }

    private void dfs(TreeNode root) {
        if (root == null)return;
        dfs(root.left);
        dfs(root.right);
        f.put(root , root.val + g.getOrDefault(root.left , 0) + g.getOrDefault(root.right , 0));
        g.put(root , Math.max(f.getOrDefault(root.left , 0) , g.getOrDefault(root.left , 0))+Math.max(f.getOrDefault(root.right , 0) , g.getOrDefault(root.right , 0)));

    }
}
